
\subsubsection{Instancias de testeo}

Realizamos 3 experimentaciones diferentes y comparamos los resultados.

La primer experimentación fue de 1000 instancias aleatorias. Cada una de las instancias cumple con que 10 <= n <= 300, 0 <= k <= n y las posiciones iniciales y finales son aleatorias entre cualquiera de los casilleros.
Los valores de n y k que elegimos se basan en que un n muy chico no reportaba tiempo de ejecución de 0 milisegundos(despreciable) y n mayor a 300, tardaba mucho en terminar. Usar valores aleatorios entre 10 y 300 nos da un espectro suficientemente amplio para visualizar el comportamiento del algoritmo. El valor de k elegido fue igual a n, para que sea posible llegar al nodo final, tanto usando todo el k como sobrando un poco también.
Usamos esta primera experimentación para comparar con las demás. 

La tercera experimentación fue de 100 instancias aleatorias tomadas también de las 1000 anteriores, pero modificamos el código, de manera que no se encuentre el camino mínimo y el algoritmo deba evaluar todos los posibles caminos. La forma en que hicimos esto fue que en el ciclo principal de búsqueda de caminos mínimos, cuando se encuentra que el nodo actual es el final, entonces se lo descarta y se continúa con el próximo nodo de la cola. Esperamos que esta experimentación muestre los peores casos del algoritmo, ya que debe evaluar todos los posibles caminos entre los nodos.

La tercera experimentación fue de 100 instancias aleatorias tomadas de las 1000 anteriores, pero usando k = 0. Esperamos obtener que usando k=0, el tiempo para encontrar un camino sea menor que usando k>0, ya que la complejidad resultaría $O(n^3)$.

\subsubsection{Resultados experimentales}

Los resultados obtenidos se pueden ver en el siguiente gráfico:

\includegraphics[scale=0.8]{ej3.png}

Hacemos unas aclaraciones sobre el gráfico.
Lo primero es que no graficamos $k * n^{3}$, sino que en vez de eso tomamos k=n y graficamos $n^{4}$. Hicimos esto porque k=n es el k máximo que elegimos para las instancias de los experimentos, entonces nos sirve para comparar con los resultados obtenidos.
También cabe aclarar que en el gráfico figuran todas la experimentaciones al mismo tiempo y esto es para poder comparar los valores obtenidos por cada una, lo cual nos pareció beneficioso, a pesar de que se pierda legibilidad.

Las conclusiones que obtenemos del gráfico son varias. 
Primero que estábamos en lo cierto con respecto al rol que cumple k, ya que esperabamos ver que la experimentación 3 mostrase un menor tiempo de ejecución al usar k=0 y así fue. Inicialmente no estábamos del todo seguros sobre esta afirmación, puesto que si k=0, los caminos mínimos pueden resultar ser mas largos, pero el gráfico confirma que nuestra suposición inicial era cierta.

La segunda conclusión que sacamos es que se ve una gran variedad de tiempos de ejecución para instancias de tamaño de entrada similar. Esto debe a la aleatoriedad de los mapas y de k, puesto que pueden darse mapas en los que sea mas difícil llegar a un camino, o sea que haya que realizar mas saltos y por ende recorrer mas casilleros hasta encontrar el nodo final.

La tercera conclusión es que hay una alta probabilidad de que el caso que supusimos peor sea efectivamente el peor caso. En el gráfico se ve que las instancias de la experimentación 2, que no encuentran el camino mínimo y evalúan todos los caminos posibles son las que tienen un mayor tiempo de ejecución.